/*
 * File:   graph.c
 * Author: aishwarya
 *
 * Created on March 12, 2011, 11:08 AM
 * Graph Implementation
 */

#include "graph.h"

/*
 * Initialize the Graph.
 */
void graph_init(GRAPH *g, int nvertices, int nedges, short is_directed) {
    int i;

    sizeof_edge = sizeof (EDGE);

    g->nvertices = nvertices;
    g->nedges = nedges;
    g->is_directed = is_directed;

    g->adj = (EDGE **) malloc((g->nvertices + 1) * sizeof (EDGE *));
    g->degree = (int *) malloc((g->nvertices + 1) * sizeof (int));

    for (i = 1; i <= g->nvertices; i++) {
        g->adj[i] = NULL;
        g->degree[i] = 0;
    }
}

/*
 * Insert an edge (u,v) at the start of the list adj[u].
 * Algorithm Design Manual, Skiena., Pg 154.
 */
void __insert_edge(GRAPH *g, int u, int v, int cost, short is_directed) {
    EDGE *e;

    e = (EDGE *) malloc(sizeof_edge);
    e->w = cost;
    e->v = v;
    e->next = g->adj[u];

    g->adj[u] = e;
    g->degree[u]++;

    /* if the graph is undirected, create another edge (v,u) */
    if (!is_directed)
        __insert_edge(g, v, u, cost, directed);
}

/*
 * Insert an edge (u,v) at the start of the list adj[u].
 */
void add_edge(GRAPH *g, int u, int v, int cost) {
    __insert_edge(g, u, v, cost, g->is_directed);
}

void graph_display(GRAPH *g) {
    EDGE *e;
    int u;

    for (u = 1; u <= g->nvertices; u++) {
        printf("%d:", u);
        e = g->adj[u];
        while (e != NULL) {
            printf(" (%d,%d)", e->v, e->w);
            e = e->next;
        }
        printf("\n");
    }
}

/*
 * Destroys the graph and frees all resources
 */
void graph_clean(GRAPH *g) {
    EDGE *e, *k;
    int u;
    for (u = 1; u <= g->nvertices; u++) {
        e = g->adj[u];
        while (e != NULL) {
            k = e;
            e = e->next;
            free(k);
        }
        g->adj[u] = NULL;
    }
    if (g->adj != NULL)
        free(g->adj);
    if (g->degree != NULL)
        free(g->degree);

    g->nvertices = g->nedges = g->is_directed = 0;
}